[线段树]数据结构C

数据结构C

Time Limit: 20 Sec Memory Limit: 512 MB

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

首先，D操作为删除操作显然不可做，又发现这道题可以离线处理，那么我们考虑倒着来，维护加入操作。

那么这时候，D操作就变为了合并操作，那么这时候我们只需要维护一个：可以支持单点修改、查询第 k 大、信息可合并的数据结构即可。

显然构建若干棵权值线段树即可！对于每个联通块维护一棵线段树，用并查集判断两点是否在一个块内。

这时候，D操作显然判断一下两点是否在一个联通块内，不在则合并两棵线段树；Q操作就是查询第 k 大，在树上二分即可；C操作就是原来值个数-1，新加入值个数+1。

Code

#include<bits/stdc++.h>
using namespace std;

const int ONE = 1000005;
const int INF = 2e6;
const int Base = 1e6;

int n, m;
int opt, x, val;
int Val[100005];
char s[5];

int Ans[300005], ans_num = 0;

int fat[100005];

int Num = 0, del[100005];
struct power {int opt, x, val;} oper[ONE];
struct point {int x, y;} a[100005];
int total = 0;
struct seg
{
    int root;
    int left, right;
    int val;
}Node[ONE * 4];

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Find(int x)
{
    if(fat[x] == x) return x;
    return fat[x] = Find(fat[x]);
}

void Un(int x, int y)
{
    int f1 = Find(x), f2 = Find(y);
    if(f1 != f2) fat[f1] = f2;
}

void Update(int &i, int l, int r, int Val, int opt) //pos = Val , + opt
{
    if(!i) i = ++total;

    Node[i].val = Node[i].val + opt;

    if(l == r) return;
    int mid = l + r >> 1;

    if(Val <= mid) Update(Node[i].left, l, mid, Val, opt);
    else Update(Node[i].right, mid + 1, r, Val, opt);

}

int Merge(int y, int x) //y merge to x
{
    if(x == 0 || y == 0) return x + y;

    Node[x].val += Node[y].val;
    Node[x].left =  Merge(Node[x].left, Node[y].left);
    Node[x].right = Merge(Node[x].right, Node[y].right);

    return x;
}

int Query(int i, int l, int r, int k) //k da
{
    if(l == r) return l;
    int mid = l + r >> 1, Val = Node[ Node[i].right ].val;

    if(k > Val)
        return Query(Node[i].left, l, mid, k - Val);
    else
        return Query(Node[i].right, mid + 1, r, k);
}

void Deal_first()
{
    for(int i = 1; i <= n; i++)
        fat[i] = i, Node[i].root = ++total;
    for(int i = 1; i <= m; i++)
        if(del[i] != 1) Un(a[i].x, a[i].y);
    for(int i = 1; i <= n; i++)
        Update(Node[Find(i)].root, 0, INF, Val[i], 1);
}

void Deal_add(int x, int y)
{
    x = Find(x), y = Find(y);
    if(x == y) return;
    Merge(Node[x].root, Node[y].root);
    fat[x] = y;
}

void Deal_query(int root, int k)
{
    root = Find(root);
    if(Node[root].val < k) {Ans[++ans_num] = 0 + Base; return;}
    Ans[++ans_num] = Query(Node[root].root, 0, INF, k);
}

void Deal_change(int x, int y) //x is point, y is need val
{
    int root = Find(x);
    Update(Node[root].root, 0, INF, Val[x], -1);
    Update(Node[root].root, 0, INF, y, 1);
    Val[x] = y;
}

int main()
{
    n = get();    m = get();

    for(int i = 1; i <= n; i++) Val[i] = get() + Base;
    for(int i = 1; i <= m; i++)
        a[i].x = get(), a[i].y = get();
    for(;;)
    {
        scanf("%s", s);
        if(s[0] == 'E') break;
        if(s[0] == 'D')
            x = get(), del[x] = 1, oper[++Num] = (power){1, x, 0};
        if(s[0] == 'Q')
            x = get(), val = get(), oper[++Num] = (power){2, x, val};
        if(s[0] == 'C')
            x = get(), val = get(), oper[++Num] = (power){3, x, Val[x]}, Val[x] = val + Base;
    }

    Deal_first();
    for(int i = Num; i >= 1; i--)
    {
        if(oper[i].opt == 1) Deal_add(a[ oper[i].x ].x, a[ oper[i].x ].y);
        if(oper[i].opt == 2) Deal_query(oper[i].x, oper[i].val);
        if(oper[i].opt == 3) Deal_change(oper[i].x, oper[i].val);
    }

    for(int i = ans_num; i >= 1; i--)
        printf("%d\n", Ans[i] - Base);
}